#-*- coding=utf-8 -*-
# py38

# 定义A：删除字符串A的任意个字符，得到的字符串B称为A的子串。
# 定义B：英文字典的排序方式，称为字典序, 例如：abc < abca < abd < ac
# 定义C：将字符串A的所有子串按照字典序排列，排最后的子串称为A的最大子串。
# 例如： jiangzemin 的最大子串是zn
# 请实现函数：
#   输入是一个字符串A，输出A的最大子串

# 从最后一个开始找最大的字符
def getMaxSubString(str):
    maxChar = ""
    result = ""
    for x in range(len(str) - 1, -1, -1):
        if str[x] >= maxChar:
            result = str[x] + result
            maxChar = str[x]
    return result


# # 使用递归的方式获取最大子串
# def getMaxSubString(str):
#     length = len(str)
#     if length <= 1:
#         return str
#     maxChar = str[0]
#     # 从起始位置开始挑选出递增的最后一个字符
#     for x in range(1, length):
#         if maxChar >= str[x]:
#             break
#         maxChar = str[x]
#         # 这里返回的理由有2个
#         # 1、字符串一直递增到最后一个，已经拿到结果了
#         # 2、此时maxChar是最后一个字符，x是最后一个字符的下标，如果不返回，会造成最后一个字符被计算2次
#         if x == length - 1:
#             return maxChar
#     subMax = getMaxSubString(str[x:])
#     if maxChar >= subMax[0]:
#         return maxChar + subMax
#     else:
#         return subMax

# # 多次遍历每次找出一个最大字符
# def getMaxSubString(str):
#     maxChar = ""
#     maxCharIndex = 0
#     for x in range(0, len(str)):
#         if str[x] <= maxChar:
#             continue
#         maxChar = str[x]
#         maxCharIndex = x
#     if maxCharIndex >= len(str) - 1:
#         return maxChar
#     return maxChar + getMaxSubString(str[maxCharIndex + 1:])

print(getMaxSubString("zzzzzzzzzzzzzz"))
